package com.zk.algorithm.string;

import com.zk.algorithm.Utils;
import com.zk.algorithm.annotation.LeetCode;

/**
 * Input: "the sky is blue",
 Output: "blue is sky the".
 *
 * @author zk
 */
@LeetCode("151")
public class ReverseWordsInAString {

    public static void main(String...args) {
        ReverseWordsInAString reverseWordsInAString = new ReverseWordsInAString();

        Utils.println(reverseWordsInAString.reverseWords("the sky is blue"));
        Utils.println(reverseWordsInAString.reverseWords("   the sky is blue   "));
        Utils.println(reverseWordsInAString.reverseWords("   the    y    is    blue   "));
    }

    // the sky is blue
    public String reverseWords(String s) {
        final StringBuilder stringBuilder = new StringBuilder(s.length());
        final char[] array = s.toCharArray();

        int i = array.length - 1;

        while (i >= 0) {
            char c = array[i];

            // 空格
            if (c == ' ') {
                i--;
                continue;
            }

            int wordEnd = i;
            int wordBegin = findWordBegin(array, i);
            appendWord(stringBuilder, array, wordBegin, wordEnd);

            // 更新 i
            i = wordBegin - 1;
        }

        return stringBuilder.toString();
    }

    private void appendWord(StringBuilder stringBuilder,
                            char[] array,
                            int wordBegin,
                            int wordEnd) {
        if (stringBuilder.length() != 0) {
            stringBuilder.append(' ');
        }

        int i = wordBegin;
        while (i <= wordEnd) {
            stringBuilder.append(array[i++]);
        }
    }

    /**
     * _abc => a
     * c => c
     *
     * @param array
     * @param i
     * @return
     */
    private int findWordBegin(char[] array, int i) {
        int wordBegin = i;

        while (wordBegin >= 0 && array[wordBegin] != ' ') {
            wordBegin--;
        }

        return wordBegin + 1;
    }

}